n = int(1e5)


def prepare(path):
    n = len(path)
    stack = [0]
    visited = [0] * n
    visited[0] = 1
    nthFathers = [[-1] for _ in range(n)]
    depth = [0] * n
    while stack:
        pt = stack.pop()
        for new_pt in path[pt]:
            if new_pt > 0 and nthFathers[new_pt][0] == -1:
                nthFathers[new_pt][0] = pt
                stack.append(new_pt)
                depth[new_pt] = depth[pt] + 1
    # If given fathers, the followings are what is needed
    tmp_still_cal = list(range(n))
    while len(tmp_still_cal):
        tmp = []
        note = []
        for i in list(tmp_still_cal):
            if nthFathers[i][-1] != -1:
                note.append(nthFathers[nthFathers[i][-1]][-1])
                tmp.append(i)
        for i, f in zip(tmp, note):
            nthFathers[i].append(f)
        tmp_still_cal = tmp
    return nthFathers, depth


path = [[] for i in range(n)]

nthFathers, depth = prepare(path)


def getNthFather(node, n):
    for i in range(len(nthFathers[node]) - 1, -1, -1):
        if n & (1 << i):
            node = nthFathers[node][i]
    return node


def getLCA(node1, node2):
    if depth[node1] > depth[node2]:
        node1 = getNthFather(node1, depth[node1] - depth[node2])
    elif depth[node2] > depth[node1]:
        node2 = getNthFather(node2, depth[node2] - depth[node1])
    if node1 == node2:
        return node1
    for i in range(len(nthFathers[node1]) - 1, -1, -1):
        if len(nthFathers[node1]) <= i: continue
        if nthFathers[node1][i] != nthFathers[node2][i]:
            node1 = nthFathers[node1][i]
            node2 = nthFathers[node2][i]
    return nthFathers[node1][0]


class LCA:

    def __init__(self, n, edges):
        self.n = n
        self.edges = edges
        self.adj = [[] for _ in range(n)]
        for u, v, _ in edges:
            self.adj[u].append(v)
            self.adj[v].append(u)
        self.depth = [0] * n
        self.parent = [[-1 for _ in range(20)] for _ in range(n)]
        # 预处理深度和父节点信息
        self.dfs(0, -1, 0)
        for j in range(1, 20):
            for i in range(n):
                if self.parent[i][j - 1] != -1:
                    self.parent[i][j] = self.parent[self.parent[i][j - 1]][j - 1]

    def dfs(self, u, p, d):
        self.parent[u][0] = p
        self.depth[u] = d
        for v in self.adj[u]:
            if v != p:
                self.dfs(v, u, d + 1)

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        for j in range(19, -1, -1):
            if self.depth[u] - (1 << j) >= self.depth[v]:
                u = self.parent[u][j]
        if u == v:
            return u
        for j in range(19, -1, -1):
            if self.parent[u][j] != self.parent[v][j]:
                u = self.parent[u][j]
                v = self.parent[v][j]
        return self.parent[u][0]
